Computer assisted animation is known. In computer assisted animation, the animator is helped by the computational power of the computer to render sequences of images which, when played back frame by frame, creates the desired animation. Creating interactive sequences of animation to replicate natural human or animal-like motion is of particular interest to the animator, and is particularly difficult to create.
Key Framing
Computer animators have traditionally used forward kinematic approaches based upon "key framing" to produce animation. Keyframing involves specifying the positions of the joints at specific instants in time during the desired motion (the key frames), then interpolating between the positions of the joints in successive key frames to generate the intermediate positions of the joints over the time interval of the desired animation. As a result, keyframing builds motion sequences frame by frame. The keyframing approach to character animation is very tedious and time consuming, often requiring several work-days of effort to produce a few seconds of animation. Keyframing also relies heavily on the artistic abilities of the animator in order to produce realistic motions that appear smooth and natural.
Motion Capture
An alternative animation method to keyframing is known as "motion capture". In this approach, sensors attached to a human actor or a mechanical device are used to record (i.e., capture) data representing the positions of the joints of a person or animal over time during the performance of a desired motion. The result is a predetermined (i.e. "canned") motion script. This "canned" motion script is then used to drive a forward kinematic model of the character in order to produce the desired animation. Although motion capture is a powerful method for reproducing complex natural human or animal-like motion, its main drawbacks are 1) the character's body configuration is restricted to be similar to that of the performer generating the motion-capture data, 2) the resulting animations are stereotypical and limited to the set of movement data collected during the motion capture session, and 3) the range of possible movements is restricted to the movements a real person or animal is capable of performing.
Inverse Kinematics
It also is known to use inverse kinematics for computer animation. In inverse kinematics (IK), a desired position and/or orientation in three-dimensional space is specified for a particular part of an articulated character's body. Inverse kinematic methods are then used to calculate body joint angles such that the particular part can be moved to the desired position and/or orientation. Inverse kinematics often is used with keyframing approaches to assist the animator in manipulating the character's body into the desired postures for the key frames, thereby allowing animated character movements to be produced with less design effort.
Traditional IK methods are based on matrix manipulations that require significant amounts of on-line computation to determine the set of joint angles that enable, for example, a character's head, hands and feet to be simultaneously placed in desired locations. When matrix inverses are used, this computational requirement grows approximately as a cubic of the number of joints in the character. For example, if a traditional IK method takes 1 millisecond of computation time for a character with 1 joint, it could take approximately 1000 milliseconds for a character with 10 joints. If the character had 100 joints, it could take approximately 1000 seconds (more than 16 minutes) to perform the same computational task. Moreover, in certain joint configurations known as singular configurations, matrix-based inverse kinematic methods can completely fail to produce a solution. And finally, traditional IK does not guarantee that the collective limb and joint movements resulting from the computed joint angle motion will be natural and life-like. This is especially true when the character has redundant joints, that is, when there are more joints than the minimum needed to perform the specified motion. Since all animals have multiply redundant joints, traditional inverse kinematics approaches have serious shortcomings when applied to the animation of human or animal-like body configurations.
Interactive Animation
In keyframing and motion capture-based approaches to animation, the resulting character animations produced are scripted and non-interactive. Consequently, for interactive applications, such as video games and virtual reality simulators, keyframing and motion capture techniques are often unsatisfactory. In an interactive video game environment, a user has total freedom to choose where to go in a three dimensional (3D) world. However, the details of how the character representing the user moves and interacts with the environment are usually determined in advance by an animator. As a result, articulated characters such as human and animal-like figures found in today's games and network applications are not fully interactive. That is, the characters have a limited set of movements, and always act and react in a stereotypical manner.
In a typical animated baseball game, for example, the batter can only swing high or low; there is no in-between. In a fighting game, the losing opponent goes down the same way; first time, every time. In addition to generating movements that are scripted, and hence predictable, current methods of producing interactive character animation are also tedious and time consuming to carry out, even for the most basic of human movements. The animator must create not only the primary movements of a character (e.g. kick, punch, block, etc.), but also all the transition motions that enable the character to arbitrarily sequence from one primary movement to another without any noticeable jumps, jerks or unnatural motions. Since the total number of these transitions can become incredibly large, even for a character with a small number of primary movements, the motions of most interactive characters today are restricted to movements between a few fixed body postures.
Behavioral Animation
A more attractive alternative to animating interactive characters with "canned" motion scripts, as in keyframing and motion capture approaches, is to use behaviors instead. Behaviors are defined as self-initiated movements generated in response to goal-based commands and interactions with the environment. Examples of behaviors are movements that enable a character to automatically "walk forward", "sit", "stand", "jump" and the like. High-level goal-based behaviors can be achieved using an integrated combination of both forward kinematics and inverse kinematics. The main advantage of animating characters using behaviors is that a potentially infinite variety of resulting movements can be created on-line, and modified in real-time. As a result, the characters produced by behavioral animation are both responsive to the user and interactive with their environment.
Behavioral animation is described in textbooks such as "Simulating Humans" by Badler, N. I., Phillips, C. B. and Webber, B. L., Oxford University Press, 1993, and "Making them Move" by Badler, N. I., Barsky, B. A. and Zeltzer, D., Morgan Kaufman Publishers, 1991. However, while a behavioral animation system in which a character is animated in response to a high-level command is simple and intuitive to describe, actual systems and software which achieve behavioral animation remain an elusive goal. The present invention achieves realistic real-time behavioral animation in interactive applications such as video games, virtual reality training simulators, world wide web browsers, and for generating computer-animated film and television productions.